/*
 * TilingSimplexNoise2D.java
 *
 * A model study for a hardware-friendly 2D simplex noise algorithm
 * that tiles over rectangular, axis-aligned periods.
 *
 * Author: Stefan Gustavson (stegu@itn.liu.se) 2006-10-17
 *
 */

public class TilingSimplexNoise2D {

  private static int grad[][] = {{2,1},{-2,1},{2,-1},{-2,-1},
                                 {1,2},{-1,2},{1,-2},{-1,-2}};

  private static int perm[] = {151,160,137,91,90,15,
  131,13,201,95,96,53,194,233,7,225,140,36,103,30,69,142,8,99,37,240,21,10,23,
  190, 6,148,247,120,234,75,0,26,197,62,94,252,219,203,117,35,11,32,57,177,33,
  88,237,149,56,87,174,20,125,136,171,168, 68,175,74,165,71,134,139,48,27,166,
  77,146,158,231,83,111,229,122,60,211,133,230,220,105,92,41,55,46,245,40,244,
  102,143,54, 65,25,63,161, 1,216,80,73,209,76,132,187,208, 89,18,169,200,196,
  135,130,116,188,159,86,164,100,109,198,173,186, 3,64,52,217,226,250,124,123,
  5,202,38,147,118,126,255,82,85,212,207,206,59,227,47,16,58,17,182,189,28,42,
  223,183,170,213,119,248,152, 2,44,154,163, 70,221,153,101,155,167, 43,172,9,
  129,22,39,253, 19,98,108,110,79,113,224,232,178,185, 112,104,218,246,97,228,
  251,34,242,193,238,210,144,12,191,179,162,241, 81,51,145,235,249,14,239,107,
  49,192,214, 31,181,199,106,157,184, 84,204,176,115,121,50,45,127, 4,150,254,
  138,236,205,93,222,114,67,29,24,72,243,141,128,195,78,66,215,61,156,180,
  151,160,137,91,90,15,
  131,13,201,95,96,53,194,233,7,225,140,36,103,30,69,142,8,99,37,240,21,10,23,
  190, 6,148,247,120,234,75,0,26,197,62,94,252,219,203,117,35,11,32,57,177,33,
  88,237,149,56,87,174,20,125,136,171,168, 68,175,74,165,71,134,139,48,27,166,
  77,146,158,231,83,111,229,122,60,211,133,230,220,105,92,41,55,46,245,40,244,
  102,143,54, 65,25,63,161, 1,216,80,73,209,76,132,187,208, 89,18,169,200,196,
  135,130,116,188,159,86,164,100,109,198,173,186, 3,64,52,217,226,250,124,123,
  5,202,38,147,118,126,255,82,85,212,207,206,59,227,47,16,58,17,182,189,28,42,
  223,183,170,213,119,248,152, 2,44,154,163, 70,221,153,101,155,167, 43,172,9,
  129,22,39,253, 19,98,108,110,79,113,224,232,178,185, 112,104,218,246,97,228,
  251,34,242,193,238,210,144,12,191,179,162,241, 81,51,145,235,249,14,239,107,
  49,192,214, 31,181,199,106,157,184, 84,204,176,115,121,50,45,127, 4,150,254,
  138,236,205,93,222,114,67,29,24,72,243,141,128,195,78,66,215,61,156,180};

  private static int mod(int x, int y) {
  	if(x < 0) return x % y + y; // Wrap to yield positive results only
  	else return x % y;
  }

  private static int fastfloor(double x) {
  	int xi = (int)x; // Cast chops off decimal part, i.e. rounds towards zero
  	return x < xi ? xi-1 : xi; // Adjust negative numbers to always round down
  	// Faster but incorrect for negative integers: return x<0 ? xi-1 : xi;
  	}

  private static double dot(int g[], double x, double y) {
    return g[0]*x + g[1]*y; // "dot(g, P)" built-in GLSL function
  }
  
  // A 2D simplex noise implementation, slightly stretched in y
  // to have a rectangular supergrid of 1:1 aspect ratio
  public static double noise(double xin, double yin)
  {
  	double n0, n1, n2; // Noise contributions from the three corners

  	// Skew the input space to determine which simplex cell we're in
  	int i = fastfloor(xin + 0.5*yin);
  	int j = fastfloor(yin);

    double x0 = -0.5*j + i; // Unskew the cell origin back to (x,y) space
    double y0 = j;
    double u0 = xin-x0; // The x,y distances from the cell origin
    double v0 = yin-y0;

    // Our simplex shape is an almost-equilateral triangle.
    // Determine which simplex we are in.
  	int i1, j1; // Offsets for second (middle) corner of simplex in (i,j) coords
    if(2.0*u0 > v0) {i1=1; j1=0;} // lower triangle, XY order: (0,0)->(1,0)->(1,1)
    else {i1=0; j1=1;}      // upper triangle, YX order: (0,0)->(0,1)->(1,1)

    // A step of (1,0) in (i,j) means a step of (1,0) in (x,y), and
    // a step of (0,1) in (i,j) means a step of (-0.5,1) in (x,y).
    double u1 = u0 - i1 + 0.5*j1; // Offsets for middle corner in (x,y) coords
    double v1 = v0 - j1;
    double u2 = u0 - 0.5; // Offsets for last corner in (x,y) coords
    double v2 = v0 - 1.0;

    // Work out the hashed gradient indices of the three simplex corners
    int i0 = i & 0xff;
    int j0 = j & 0xff;
    int gi0 = perm[i0+perm[j0]] & 0x07;
    int gi1 = perm[i0+i1+perm[j0+j1]] & 0x07;
    int gi2 = perm[i0+1+perm[j0+1]] & 0x07;

    // Calculate the contribution from the three corners
    double t0 = 0.7 - u0*u0 - v0*v0;
    if(t0<0) n0 = 0.0;
    else {
      t0 *= t0;
      n0 = t0 * t0 * dot(grad[gi0], u0, v0);
    }

    double t1 = 0.7 - u1*u1 - v1*v1;
    if(t1<0) n1 = 0.0;
    else {
      t1 *= t1;
      n1 = t1 * t1 * dot(grad[gi1], u1, v1);
    }

    double t2 = 0.7 - u2*u2 - v2*v2;
    if(t2<0) n2 = 0.0;
    else {
      t2 *= t2;
      n2 = t2 * t2 * dot(grad[gi2], u2, v2);
    }

    // Add contributions from each corner to get the final noise value
    return 10.0 * (n0 + n1 + n2);
  }

  // A 2D simplex noise implementation that tiles over a rectangular grid
  // with any integer period in x and any even integer period in y
  // NOTE 1: This tiles correctly for any integer period in x and any even
  // integer period in y, but for better speed, periods that are powers of two
  // can be implemented by bitmasking instead of modulus operations.
  // Bitmasking is a lot faster and hardware friendly than a general modulus.
  // NOTE 2: Java's division remainder operation '%' is not a modulus operator,
  // it gives negative results for negative numbers, which is wrong here.
  // NOTE 3: There is still a bug in here: the pattern is slightly different for
  // the four quadrants, so regions which include the lines x=0 or y=0 won't tile!
  
  public static double noise(double xin, double yin, int xperiod, int yperiod)
  {
  	double n0, n1, n2; // Noise contributions from the three corners

  	// Skew the input space to determine which simplex cell we're in
  	int i = fastfloor(xin + 0.5*yin);
  	int j = fastfloor(yin);

    double x0 = -0.5*j + i; // Unskew the cell origin back to (x,y) space
    double y0 = j;
    double u0 = xin - x0; // The x,y distances from the cell origin
    double v0 = yin - y0;

    // Our simplex shape is an almost-equilateral triangle.
    // Determine which simplex we are in.
  	int i0, j0; // Indices for first corner of simplex in (i,j) coords
  	int i1, j1; // Offsets for second corner of simplex in (i,j) coords
  	int i2, j2; // Offsets for third corner of simplex

    // Skew the i,j indexing to line up with the rectangular tiling grid
	i0 = i - fastfloor(0.5*j); // j/2 is not the same as floor(0.5*j) if j<0
	j0 = j;

    if( 2.0*u0 > v0 ) { i1=1; j1=0; } // lower triangle, +i,+j traversal
    else { i1=0; j1=1; }              // upper triangle, +j,+i traversal

  	i2 = 1; // i2 is changed below for odd rows
  	j2 = 1; // j2 is always 1, could actually be replaced by a constant

    // A step of 1 in i means a step of (1,0) in (x,y), and
    // a step of 1 in j means a step of (-0.5,1) in (x,y).
    double u1 = u0 - i1 + 0.5*j1; // Offsets for middle corner in (x,y) coords
    double v1 = v0 - j1;
    double u2 = u0 - 0.5;     // Offsets for last corner in (x,y) coords
    double v2 = v0 - 1;

    // Adjust gradient indexing of every 2nd simplex row to tile with the
    // row above, by skewing the i1, i2 offsets one step extra at the top.
	if((j0&1) == 1) {	// if j0 is odd
        i2 = 0;              // the last corner has same i index as the first
		if(i1 == 0) i1 = -1; // if the traversal is +j,+i, i first decreases
    }

    // Work out the hashed gradient indices of the three simplex corners
    int gi0 = perm[mod(i0, xperiod) + perm[mod(j0, yperiod)]] & 0x07;
    int gi1 = perm[mod(i0 + i1, xperiod) + perm[mod(j0 + j1, yperiod)]] & 0x07;
    int gi2 = perm[mod(i0 + i2, xperiod) + perm[mod(j0 + j2, yperiod)]] & 0x07;

    // Faster version that works only for periods that are powers of 2:
/*
	int xmask = xperiod - 1; // This requires that xperiod is 2^n, n>=1
	int ymask = yperiod - 1; // This requires that yperiod is 2^n, n>=1
    int gi0 = perm[(i0 & xmask) + perm[(j0 & ymask)]] & 0x07;
    int gi1 = perm[((i0 + i1) & xmask) + perm[(j0 + j1) & ymask]] & 0x07;
    int gi2 = perm[((i0 + i2) & xmask) + perm[(j0 + j2) & ymask]] & 0x07;
*/

    // Calculate the contribution from the three corners
    double t0 = 0.7 - u0*u0 - v0*v0;
    if(t0<0) n0 = 0.0;
    else {
      t0 *= t0;
      n0 = t0 * t0 * dot(grad[gi0], u0, v0);
    }

    double t1 = 0.7 - u1*u1 - v1*v1;
    if(t1<0) n1 = 0.0;
    else {
      t1 *= t1;
      n1 = t1 * t1 * dot(grad[gi1], u1, v1);
    }

    double t2 = 0.7 - u2*u2 - v2*v2;
    if(t2<0) n2 = 0.0;
    else {
      t2 *= t2;
      n2 = t2 * t2 * dot(grad[gi2], u2, v2);
    }

    // Add contributions from each corner to get the final noise value
    return 10.0 * (n0 + n1 + n2);
  }

  public static double index(double xin, double yin, int xperiod, int yperiod)
  {
  	double n0, n1, n2; // Noise contributions from the three corners

  	// Skew the input space to determine which simplex cell we're in
  	int i = fastfloor(xin + 0.5*yin);
  	int j = fastfloor(yin);

    double x0 = -0.5*j + i; // Unskew the cell origin back to (x,y) space
    double y0 = j;
    double u0 = xin - x0; // The x,y distances from the cell origin
    double v0 = yin - y0;

    // Our simplex shape is an almost-equilateral triangle.
    // Determine which simplex we are in.
  	int i0, j0; // Indices for first corner of simplex in (i,j) coords
  	int i1, j1; // Offsets for second corner of simplex in (i,j) coords
  	int i2, j2; // Offsets for third corner of simplex

    // Skew the i,j indexing to line up with the rectangular tiling grid
	i0 = i - fastfloor(0.5*j); // j/2 is not the same as floor(0.5*j) if j<0
	j0 = j;

    if( 2.0*u0 > v0 ) { i1=1; j1=0; } // lower triangle, +i,+j traversal
    else { i1=0; j1=1; }              // upper triangle, +j,+i traversal

  	i2 = 1; // i2 is changed below for odd rows
  	j2 = 1; // j2 is always 1, could actually be replaced by a constant

    // A step of 1 in i means a step of (1,0) in (x,y), and
    // a step of 1 in j means a step of (-0.5,1) in (x,y).
    double u1 = u0 - i1 + 0.5*j1; // Offsets for middle corner in (x,y) coords
    double v1 = v0 - j1;
    double u2 = u0 - 0.5;     // Offsets for last corner in (x,y) coords
    double v2 = v0 - 1;

    // Adjust gradient indexing of every 2nd simplex row to tile with next
    // row, by skewing the i1, i2 offsets one step extra at the top.
	if((j0&1)==1) {	// if j0 is odd
        i2 = 0;              // the last corner has same i index as the first
		if(i1 == 0) i1 = -1; // if the traversal is +j,+i, i first decreases
    }

    // Work out the hashed gradient indices of the three simplex corners
    int gi0 = perm[mod(i0, xperiod) + perm[mod(j0, yperiod)]] & 0x07;
    int gi1 = perm[mod(i0 + i1, xperiod) + perm[mod(j0 + j1, yperiod)]] & 0x07;
    int gi2 = perm[mod(i0 + i2, xperiod) + perm[mod(j0 + j2, yperiod)]] & 0x07;

	double d0 = u0*u0+v0*v0;
	double d1 = u1*u1+v1*v1;
	double d2 = u2*u2+v2*v2;
	return 0.125 * (d0<d1 ? (d0<d2 ? gi0 : d1<d2 ? gi1 : gi2) : (d1<d2 ? gi1: gi2));

  }

}
